\section{Problem Statements and Our Results}\label{sec:results}
We formally state the problems and our main results.
\paragraph{The Single Random Walk problem} Given a $d$-regular dynamic graph $\mathcal{G} = (V, E_t)$ and a starting node $s \in V$, our goal is to devise a fast distributed  {\em random walk} algorithm such that, at the end, a destination node, sampled from a $\tau$-length walk, outputs the source node's ID (equivalenly, one can require $s$ to output the destination node's ID), where $\tau$ is (an upper bound on) the dynamic mixing time of $\mathcal{G}$ (cf. Section \ref{mixing_time}), under the assumption that $\mathcal{G}$ is modified by an oblivious adversary (cf. Section \ref{sec:model}). Note that this
distribution will be ``close" to the stationary distribution of $\mathcal{G}$ (stationary distribution and $\tau$
are both well-defined  --- cf. Section  \ref{mixing_time}).  
Since we are assuming a $d$-regular dynamic graph,  our goal is to sample from (or close to) the uniform distribution (which is the stationary distribution) using as few rounds as possible. Note that we would like to sample fast via  random walk --- this is also necessary for
the applications considered in this paper. On the other hand, if one had to simply get a  uniform random sample, it can be accomplished by other means, e.g.,
it is easy to obtain it in $O(\Phi)$ rounds (by using flooding).

For clarity, observe that the following naive algorithm solves the
above problem in $O(\tau)$ rounds: The walk of length $\tau$ is
performed by sending a token for $\tau$ steps, picking a random
neighbor in each step. Then, the destination node $v$ of this walk
outputs the ID of $s$.
Our goal is to perform such sampling with significantly less number
of rounds, i.e., in time that is sub-linear in $\tau$, in the CONGEST model, and  using  random walks rather than naive flooding techniques. As mentioned earlier this is needed for the application discussed in this paper. Our  result is as follows. 
\begin{theorem}\label{thm:maintheorem}
The algorithm {\sc Single-Random-walk} (cf. Algorithm \ref{alg:single-random-walk}) solves the Single Random Walk problem in a dynamic graph and with high probability finishes in $\tilde{O}(\sqrt{\tau \Phi})$ rounds. 
\end{theorem}

The above algorithm assumes that nodes have knowledge of $\tau$ and the dynamic diameter $\Phi$ (or at least some good estimate of these parameters). In many applications, it is easy to have a good estimate of  $\tau$  and $\Phi$ when there is knowledge of the structure of the individual graphs --- e.g.,  each $G_t$ is an expander as in \cite{JGPE:soda12,FOCS2001} or a grid graph.  Notice that in the worst case the value of $\tau$ is $\tilde{\Theta}(n^2)$, and hence this bound can be used even if nodes have no knowledge. Therefore putting $\tau = \tilde{\Theta}(n^2)$ in the above Theorem \ref{thm:maintheorem}, we see that our algorithm samples a node from the uniform distribution through a random walk in $\tilde O(n \sqrt{\Phi})$ rounds w.h.p. (As mentioned earlier, $\Phi$ is at most $n$. Also, we note that always, $\tau \geq \Phi$.)  Our algorithm is better than the naive approach when $\Phi \le \tau/\polylog n$. (The naive approach takes $\tau$ rounds to sample a node). Further, in the worst case, the value of $\tau$ could be $O(n^2)$. Therefore putting $\tau = O(n^2)$ in the above bound, we see that our algorithm can sample a node uniformly through random walk in $\tilde O(n \sqrt{\Phi})$ rounds w.h.p., whereas the naive approach will take $O(n^2)$ rounds. Also $\Phi$ could be as large as $n$ in worst case.  
Our algorithm can be generalized to work for non-regular dynamic graphs also (cf. Section \ref{sec:nonregular}).

We also consider the following extension of the Single Random Walk problem,
called the  {\em $\kappa$ Random Walks problem}: We have $\kappa$ sources $s_1, s_2, ..., s_{\kappa}$ and we want each of 
the $\kappa$ destinations to output an ID of its corresponding source, assuming that each source initiates an independent
random walk of length $\tau$. Equivalently, one can ask each source to output the ID of its corresponding destination. The goal is to output all the ID's in as few rounds as possible. We show that:

\begin{theorem}\label{thm:kwalks} The algorithm {\sc Many-Random-Walks} (cf. Algorithm \ref{alg:many-random-walk}) solves the $\kappa$ Random Walks problem in a dynamic graph and with high probability finishes in
$\tilde O\left(\min \{\sqrt{\kappa \tau \Phi}, \kappa + \tau\} \right)$ rounds, where $\kappa = O(\frac{n^2d^2\Phi}{\tau})$ and  assuming that the source nodes are chosen uniformly at random. If the source nodes are chosen arbitrarily, then we  show that the   $\kappa$ Random Walks problem (for any $\kappa$) can be solved in $\tilde{O}(\kappa \sqrt{\tau \Phi})$ rounds with high probability. 
\end{theorem}



\paragraph{Information dissemination (or $k$-gossip) problem} In $k$-gossip, initially $k$ different tokens are assigned to a set $V$ of $n$ nodes. A node may have more than one token. The  goal is to disseminate all the $k$ tokens to all the $n$ nodes. We present a fast distributed randomized algorithm for $k$-gossip in a dynamic network. Our algorithm uses {\sc Many-Random-Walks} as a key subroutine; this is the first sub-quadratic time fully-distributed {\em token forwarding} algorithm. In particular, we present algorithm for the $k$-gossip problem assuming the tokens are initially distributed among the source nodes (each of which has some  tokens to disseminate) that are chosen uniformly at random. We show the following result: 

%%%Removing below for the case 1 %%%
\iffalse
If $k$ tokens are initially situated among nodes (may not be distinct) arbitrarily then we show the following result. 
\begin{theorem}\label{thm:token-bound1}
The  $k$-gossip problem can be solved  with high probability in $\tilde{O}(\min\{k n^{\frac{1}{2}}(\tau \Phi)^{\frac{1}{4}}, k\Phi \})$ rounds. 
\end{theorem}
\fi

\begin{theorem}\label{thm:token-bound}
There is a distributed algorithm that solves the {\em $k$-gossip} problem in a dynamic graph with high probability in $\tilde{O}(\min\{n^{\frac{1}{3}}k^{\frac{2}{3}}(\tau \Phi)^{\frac{1}{3}}, k\Phi \})$ rounds, assuming that  the source node for each token  is chosen uniformly at random. 
\end{theorem}


\iffalse
\paragraph{Mixing time estimation.} Given a dynamic network, we are interested in  (approximately) computing the dynamic mixing time, assuming that the mixing time of the (individual) graphs do not change. We present an efficient distributed algorithm  for estimating the mixing time. In
particular, we show the following result where $\tau^x_{mix}$ is the dynamic mixing time with respect to a starting node $x$. We formally define these notions in Section~\ref{mixing_time}.
This gives an alternative algorithm to the only previously known
approach by Kempe and McSherry \cite{kempe}  that can be used to estimate
$\tau^x_{mix}$ in a {\em static} graph in $\tilde O(\tau^x_{mix})$ rounds. 
%\vspace{-0.05in}
\begin{theorem}\label{thm:complexity_bound_mixing_time}
Given connected $d$-regular dynamic graph with dynamic diameter $\Phi$, a node $x$ can find, in $\tilde{O}(n^{1/4}\sqrt{\Phi \tau^x(\epsilon)})$ rounds, a time
$\tilde{\tau}^x_{mix}$ such that $\tau^x_{mix}\leq \tilde{\tau}^x_{mix}\leq \tau^x(\epsilon)$, where $\epsilon = \frac{1}{6912e\sqrt{n}\log n}$.
\end{theorem}



\noindent {\bf Our Contributions.}
\begin{itemize}
\item We present an efficient distributed algorithm to sample from uniform distribution in dynamic networks.
\item We present a fast distributed randomized algorithm for the fundamental problem of {\em information dissemination} in a dynamic networks. Our algorithm is based on performing random walks in networks; to the best of our knowledge, this is the first subquadratic time fully-distributed {\em token forwarding} algorithm.
\item We also present a simple and fast distributed algorithm for estimating the dynamic mixing time and  related spectral properties of the underlying dynamic network.
\end{itemize}  
\fi

